#include<decisiontree/DecisionTree.h>
#include<set>
#include<map>
#include<iostream>
using namespace std;
Node* DecisionTree::creat(){
	/**
	 * 将所有的y放入C内
	 */
	// set<double> C;
	// for(int i=0;i<datas->getLen();i++){
	// 	C.insert(datas->getData(i).y);
	// }
	vector<int> index_data;
	for(int i=0;i<datas->getLen();i++){
		index_data.push_back(i);
	}
	vector<int> index_feature;
	for(int i=0;i<features->size();i++){
		index_feature.push_back(i);
	}
	Node* root = createNode(index_data,index_feature,-1.0);

	return root;
}

Node* DecisionTree::createNode(vector<int> index_data,vector<int> index_feature,double value){
	Node * result = new Node();
	result->setSelectValue(value);
	map<double,int> C;
	for(int i=0;i<index_data.size();i++){
		double label = datas->getData(index_data[i]).y;
		if(C.find(label)==C.end()){
			C[label]=0;
		}
		C[label]=C[label]+1;
	}
	if(C.size()==1){
		result->setLabel((*C.begin()).first);
		return result;
	}
	map<double,int>::iterator iter = C.begin();
	int max=0;
	double maxLable=-1.0;
	while(iter!=C.end()){
		if(iter->second>max){
			max = iter->second;
			maxLable = iter->first;
		}
		iter++;
	}
	if(index_feature.size()==0){
		result->setLabel(maxLable);
		return result;
	}
	double max_gain = 0.0;
	int select = -1;
	for(int i=0;i<index_feature.size();i++){
		double ent_gain = selectFun(index_data,index_feature[i]);
		if(ent_gain>=max_gain){
			select = i;
			max_gain = ent_gain;
		}
	}
	result->setFeature(index_feature[select]);
	result->setLabel(maxLable);
	if(max_gain<epsoion){
		return result;
	}
	/**/
	Feature feature = (*features)[select];
	map<double,vector<int> > feature_data;
	for(int i=0;i<index_data.size();i++){
		double key = feature.value(datas->getData(index_data[i]).x->get(select));
		if(feature_data.find(key)==feature_data.end()){
			vector<int> single;
			feature_data[key]=single;
		}
		feature_data[key].push_back(index_data[i]);
	}
	result->setFeature(select);
	index_feature.erase(index_feature.begin()+select);
	map<double,vector<int> >::iterator itter = feature_data.begin();
	for(;itter!=feature_data.end();itter++){
		result->addChild(createNode(itter->second,index_feature,itter->first));
	}
	return result;
}

void DecisionTree::decision(Data& data,Node* root){
	vector<Node*> children = root->getChildren();
	if(children.size()==0){
		data.y = root->getLabel();
	}
	else{
		int feature_index = root->getFeature();
		double value = data.x->get(feature_index);
		for(int i=0;i<children.size();i++){
			if(value==children[i]->getSelectValue()){
				decision(data,children[i]);
			}
		}
	}
}

void DecisionTree::print(Node* root){
	if(NULL==root){
		return;
	}
	cout<<"Label:"<<root->getLabel()<<",Feature:"<<root->getFeature()<<",Value:"<<root->getSelectValue()<<endl;
	for(int i=0;i<root->getChildren().size();i++){
		print(root->getChildren()[i]);
	}
}
